package Hot100;

import common.ListNode;

/**
 * @author zhangmin
 * @create 2021-12-30 13:45
 */
public class sortList148 {

    /**
     * 148. 排序链表
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     * 1、转换成数组，排序后构建链表
     * 2、归并排序
     * */
    ListNode sortList(ListNode head,ListNode tail){
        if (head==null) return head;
        if (head.next==tail){
            head.next=null;
            return head;
        }
        //使用双指针，找到链表head到tail间的中间节点
        ListNode slow=head,fast=head;
        while (fast!=tail){
            slow=slow.next;
            fast=fast.next;
            if (fast!=tail){
                fast=fast.next;
            }
        }
        ListNode mid=slow;
        ListNode list1=sortList(head,slow);
        ListNode list2=sortList(slow,tail);
        ListNode merged=merge(list1,list2);
        return merged;
    }

    ListNode merge(ListNode list1,ListNode list2){
        if (list1==null) return list2;
        if (list2==null) return list1;
        ListNode tempHead=new ListNode(-1);
        ListNode temp=tempHead,p1=list1,p2=list2;
        while (p1!=null&&p2!=null){
            if (p1.val<=p2.val){
                temp.next=p1;
                p1=p1.next;
            }else {
                temp.next=p2;
                p2=p2.next;
            }
            temp=temp.next;
        }
        if (p1!=null) temp.next=p1;
        else if (p2!=null){
            temp.next=p2;
        }
        return tempHead.next;
    }

    public ListNode sortList1(ListNode head) {
       return sortList(head,null);
    }

    //2、自底向上归并排序,先计算链表长度，然后分子链表计算
    //子链表长度为subLen
    public ListNode sortList(ListNode head) {
        if (head==null) return head;
        int len=0;
        ListNode node=head;
        while (node!=null){
            len++;
            node=node.next;
        }
        ListNode tempHead=new ListNode(-1,head);
        for (int subLen = 1; subLen < len; subLen<<=1) {
            ListNode pre=tempHead,cur=tempHead.next;
            while (cur!=null){
                ListNode head1=cur;
                //划分出第一个subLen
                for (int i = 1; i < subLen&&cur.next!=null; i++) {
                    cur=cur.next;
                }
                ListNode head2=cur.next;
                cur.next=null;
                cur=head2;
                //划分出第2个subLen
                for (int i = 1; i < subLen&&cur!=null&&cur.next!=null; i++) {
                    cur=cur.next;
                }
                ListNode next=null;
                if (cur!=null){
                    next=cur.next;
                    cur.next=null;
                }
                //合并连个sublist
                ListNode merged=merge(head1,head2);
                pre.next=merged;
                while (pre.next!=null){
                    pre=pre.next;
                }
                cur=next;
            }
        }
        return tempHead.next;
    }

}
